import java.util.ArrayList;
import java.util.List;

public class 从栈中取出K个硬币的最大面值和 {
    public int maxValueOfCoins(List<List<Integer>> piles, int m) {
        // 从前 i 个里面拿 j 个拿到的最大值
        int n = piles.size();
        piles.add(0,new ArrayList<>());
        int[][] dp = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            List<Integer> list = piles.get(i);
            int t = Math.min(m,list.size());
            // 前缀和预处理, 为了加速
            int[] preSum = new int[t + 1];
            int sum = 0;
            for (int j = 0; j < t; j++) {
                sum += list.get(j);
                preSum[j + 1] = sum;
            }
            for (int j = 0; j <= m; j++) {
                // 不拿硬币
                dp[i][j] = dp[i - 1][j];
                for (int k = 1; k <= Math.min(t,j); k++) {
                    dp[i][j] = Math.max(dp[i][j],dp[i - 1][j - k] + preSum[k]);
                }
            }
        }
        return dp[n][m];
    }
}
